package ai.zixing.mashibing.basic_class.class07;

// 给你二叉树中的某个节点，返回该节点的后继节点
// Node 中有属性 parent
public class Code07_SuccessorNode {

    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return null;
        }
        // 右数不为空
        if (node.right != null) {
            // 【左头右】左树上最后打印的节点，就是当前节点的后续节点
            return getLeftMost(node.right);
        }
        // 没有右树
        else{
            Node parent = node.parent;
            // 当前节点是其父接点的右孩子
            // 如果父节点不为空，左孩子不是自（自己是右孩子)，继续上找
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            // 父节点是空也返回（整棵树的最右节点）
            return parent;
        }
    }

    // 找到一个节点的第一个左孩子
    public static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}
